#include<stdio.h>
#include<stdlib.h>
#include<vector>
using namespace std;

void swap(int &a,int &b){
    int temp=a;
    a=b;
    b=temp;
}
int partition(vector<int> &ve,int l,int r){
    int i=l,j=r;
    while(i<j){
        while(i<j && ve[j]>=ve[l]) j--;
        while(i<j && ve[i]<=ve[l]) i++;
        swap(ve[i],ve[j]);
    }
    swap(ve[i],ve[l]);
    return i;
}
void quickSort(vector<int>& ve,int l,int r){
    // 子数组长度为 1 时终止递归
    if(l>=r) return ;
    // 哨兵划分操作
    int i = partition(ve, l, r);
    quickSort(ve,l,i-1);
    quickSort(ve,i+1,r);
}
int binary_Search(vector<int> ve,int k,int len){
    int l=0,r=len-1;
    int mid=(l+r)/2;
    while(l<=r){
        mid=l+(r-l)/2;
        if(k<ve[mid]) r=mid-1;
        else if(k>ve[mid]) l=mid+1;
        else return mid;
    }
    // return l;//返回插入位置
    return -1;
}
void print_Ve(vector<int> ve){
    for(vector<int>::iterator it=ve.begin();it!=ve.end();it++){
        printf("%d ",*it);
    }
}
int main(){
    vector<int> ve={1,5,6,7,8,3,2,4};
    quickSort(ve,0,ve.size()-1);
    print_Ve(ve);
    int res=binary_Search(ve,3,ve.size());
    printf("\npos:%d,ve[pos]=%d",res,ve[res]);
    return 0;
}